package it.unisa.ingegneria.tdp.esercitazione3;
import java.util.Comparator;
import java.util.Iterator;



public class BinarySearchTree<K extends Comparable<K>, V> extends
LinkedBinaryTree<Entry<K, V>> implements Dictionary<K, V> {

	protected int numEntries = 0;

	public BinarySearchTree() {
		try {
			addRoot(null);
		} catch (NonEmptyTreeException e) {
			e.printStackTrace();
		}
	}

	public BinarySearchTree(Comparator<K> c) {
		try {
			addRoot(null);
		} catch (NonEmptyTreeException e) {
			e.printStackTrace();
		}
	}

	protected K key(Position<Entry<K, V>> position)
			throws InvalidPositionException {
		return position.element().getKey();
	}

	protected V value(Position<Entry<K, V>> position)
			throws InvalidPositionException {
		return position.element().getValue();
	}

	protected Entry<K, V> entry(Position<Entry<K, V>> position)
			throws InvalidPositionException {
		return position.element();
	}

	protected void replaceEntry(Position<Entry<K, V>> pos, Entry<K, V> ent)
			throws InvalidPositionException {
		((BSTEntry<K, V>) ent).pos = pos;
		replace(pos, ent);
	}

	protected void checkEntry(Entry<K, V> ent) throws InvalidEntryException {

		if (ent == null || !(ent instanceof BSTEntry))
			throw new InvalidEntryException("Entry non valida.");
	}

	protected void checkKey(K key) throws InvalidKeyException {

		if (key == null)
			throw new InvalidKeyException("Chiave uguale a null.");
		try {
			key.compareTo(key);
		} catch (Exception e) {
			throw new InvalidKeyException("Chiave non valida.");
		}
	}

	// Metodo ausiliario per trovare la posizione di inserimento data la chiave
	protected Position<Entry<K, V>> treeSearch(K key, Position<Entry<K, V>> pos)
			throws InvalidPositionException, BoundaryViolationException {

		if (isExternal(pos)) {
			return pos;
		} else {
			K curKey = key(pos);
			int comp = key.compareTo(curKey);
			if (comp < 0) {
				return treeSearch(key, left(pos));
			} else if (comp > 0) {
				return treeSearch(key, right(pos));
			}
			return pos;
		}
	}

	// Metodo ausiliario per inserire un'entrata in una foglia
	protected Entry<K, V> insertAtExternal(Position<Entry<K, V>> v,
			Entry<K, V> e) throws InvalidPositionException {
		expandExternal(v, null, null);
		replace(v, e);
		numEntries++;

		return e;
	}

	// Rimuovo la foglia v e il padre di v
	protected void removeExternal(Position<Entry<K, V>> v)
			throws InvalidPositionException, BoundaryViolationException {

		if (!isExternal(v))
			throw new InvalidPositionException("Il nodo non e` una foglia");

		BTNode<Entry<K, V>> p = (BTNode<Entry<K, V>>) parent(v);
		BTNode<Entry<K, V>> s = (BTNode<Entry<K, V>>) sibling(v);

		if (isRoot(p)) {
			s.setParent(null);
			root = s;
		} else {
			BTNode<Entry<K, V>> g = (BTNode<Entry<K, V>>) parent(p);

			if (p == left(g)) {
				g.setLeft(s);
			} else {
				g.setRight(s);
			}

			s.setParent(g);
		}

		size = size - 2;
	}

	// Aggiunge a L tutte le entry nel sottoalbero avente come radice v e avente
	// chiavi uguali a k
	protected void addAll(PositionList<Entry<K, V>> L, Position<Entry<K, V>> v,
			K k) throws InvalidPositionException, BoundaryViolationException {
		if (isExternal(v)) {
			return;
		}

		Position<Entry<K, V>> pos = treeSearch(k, v);
		if (!isExternal(pos)) {
			addAll(L, left(pos), k);
			L.addLast(pos.element());
			addAll(L, right(pos), k);
		}
	}

	public int size() {
		return numEntries;
	}

	public boolean isEmpty() {
		return (size() == 0);
	}

	public Entry<K, V> find(K key) throws InvalidKeyException {

		checkKey(key);
		Position<Entry<K, V>> curPos;

		try {
			curPos = treeSearch(key, root());

			if (isInternal(curPos)) {
				return entry(curPos);
			}

		} catch (InvalidPositionException | BoundaryViolationException
				| EmptyTreeException e) {
			e.printStackTrace();
		}

		return null;
	}

	public Iterable<Entry<K, V>> findAll(K key) throws InvalidKeyException {
		checkKey(key);
		PositionList<Entry<K, V>> L = new NodePositionList<Entry<K, V>>();

		try {
			addAll(L, root(), key);
		} catch (InvalidPositionException | BoundaryViolationException
				| EmptyTreeException e) {
			e.printStackTrace();
		}
		return L;
	}

	public Entry<K, V> insert(K k, V v) throws InvalidKeyException {
		checkKey(k);
		try{
			Position<Entry<K, V>> insPos= treeSearch(k,root());

			while (!isExternal(insPos)) {
				insPos = treeSearch(k, left(insPos));
			}

			return insertAtExternal(insPos, new BSTEntry<K, V>(k, v, insPos));
		}
		catch(InvalidPositionException e){
			e.printStackTrace();
		} catch (BoundaryViolationException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (EmptyTreeException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return null;
	}

	// Restituisce l'entrata con chiave k dopo averla cancellata; altrimenti
	// restituisce null. Da ricordare che la cancellazione e' intesa su albero
	// binario
	public Entry<K, V> remove(Entry<K, V> ent) throws InvalidEntryException {

		checkEntry(ent);
		Position<Entry<K, V>> remPos = ((BSTEntry<K, V>) ent).position();
		Entry<K, V> toReturn = ent;

		try {
			if (isExternal(left(remPos))) { // Caso 1: uno dei due figli � una
				// foglia
				remPos = left(remPos);
			} else if (isExternal(right(remPos))) {
				remPos = right(remPos);
			} else { // Caso 2: entrambi i figli sono nodi interni
				Position<Entry<K, V>> swapPos = remPos;
				// cerca il successore di ent
				remPos = right(swapPos);

				do {
					remPos = left(remPos);
				} while (isInternal(remPos)); // Si ferma quando remPos e` una
				// foglia

				replaceEntry(swapPos, parent(remPos).element());
			}

			removeExternal(remPos);

		} catch (InvalidPositionException | BoundaryViolationException e) {
			e.printStackTrace();
		}
		numEntries--;

		return toReturn;
	}

	// Restituisce una collezione iterabile di tutte le entrate del dizionario
	public Iterable<Entry<K, V>> entries() {
		Iterable<Position<Entry<K, V>>> positions = positions();

		PositionList<Entry<K, V>> elements = new NodePositionList<Entry<K, V>>();
		Iterator<Position<Entry<K, V>>> it = positions.iterator();

		while (it.hasNext()) {
			try {
				elements.addLast(it.next().element());
			} catch (InvalidPositionException e) {
				e.printStackTrace();
			}
		}

		return elements;
	}

	protected static class BSTEntry<K extends Comparable<K>, V> implements
	Entry<K, V> {

		// Ho un riferimento a position che e' un'autoreferenziazione al BTNode
		// che
		// contiene la BSTEntry
		protected K key;
		protected V value;
		protected Position<Entry<K, V>> pos;

		BSTEntry() {

		}

		BSTEntry(K k, V v, Position<Entry<K, V>> p) {
			key = k;
			value = v;
			pos = p;
		}

		public K getKey() {
			return key;
		}

		public V getValue() {
			return value;
		}

		public Position<Entry<K, V>> position() {
			return pos;
		}

		@Override
		public int compareTo(Entry<K, V> arg0) {
			return key.compareTo(arg0.getKey());
		}
	}

}
